Analyzing the effect of local rounding error propagation on the maximal attainable accuracy of the pipelined Conjugate Gradient method

摘要

Pipelined Krylov subspace methods typically offer improved strong scaling onparallel HPC hardware compared to standard Krylov subspace methods for largeand sparse linear systems. In pipelined methods the traditional synchronizationbottleneck is mitigated by overlapping time-consuming global communicationswith useful computations. However, to achieve this communication hidingstrategy, pipelined methods introduce additional recurrence relations for anumber of auxiliary variables that are required to update the approximatesolution. This paper aims at studying the influence of local rounding errorsthat are introduced by the additional recurrences in the pipelined ConjugateGradient method. Specifically, we analyze the impact of local round-off effectson the attainable accuracy of the pipelined CG algorithm and compare to thetraditional CG method. Furthermore, we estimate the gap between the trueresidual and the recursively computed residual used in the algorithm. Based onthis estimate we suggest an automated residual replacement strategy to reducethe loss of attainable accuracy on the final iterative solution. The resultingpipelined CG method with residual replacement improves the maximal attainableaccuracy of pipelined CG, while maintaining the efficient parallel performanceof the pipelined method. This conclusion is substantiated by numerical resultsfor a variety of benchmark problems.